package Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class N皇后 {

    static List<List<String>> res=new ArrayList<>();
    static public List<List<String>> solveNQueens(int n) {
        char[][] track=new char[n][n];
        for (char[] a:track){
            Arrays.fill(a,'.');
        }
        back(0,n,track);
        return  res;
    }

    static void back(int row,int cols,char[][] track){
        if(row==cols){
            res.add(toList(track));
        }
        for(int i=0;i<cols;i++){
            if(!isvaild(track,row,i)){
                continue;
            }else {
                track[row][i]='Q';
                back(row+1,cols,track);
                track[row][i]='.';
            }
        }
    }

    static List toList(char[][] track){
        List<String> list=new ArrayList<>();
        for (char[] a:track){
            StringBuilder temp=new StringBuilder();
            for(char c:a){
                temp.append(c);
            }
            list.add(temp.toString());
        }
        return list;
    }

    static boolean isvaild(char[][] track,int row,int col){
        int len=track.length;
        for (int i=0;i<len;i++){
            if(track[i][col]=='Q') return false;
        }
        for (int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(track[i][j]=='Q') return false;
        }
        for (int i=row-1,j=col+1;i>=0&&j<len;i--,j++){
            if(track[i][j]=='Q') return false;
        }
        return true;
    }
    public static void main(String[] args) {

        for (List<String> list : solveNQueens(4)) {
            for (String s : list) {
                System.out.print(s+" ");
                System.out.println();
            }
        }
    }

}